package likouJava;

import java.util.HashMap;
import java.util.Map;

public class 路径总和III {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, 0L, targetSum, prefix);
    }

    private int dfs(TreeNode node, long curSum, int targetSum, Map<Long, Integer> prefix) {
        if (node == null) return 0;

        curSum += node.val;
        int res = prefix.getOrDefault(curSum - targetSum, 0);

        prefix.put(curSum, prefix.getOrDefault(curSum, 0) + 1);

        res += dfs(node.left, curSum, targetSum, prefix);
        res += dfs(node.right, curSum, targetSum, prefix);

        prefix.put(curSum,prefix.get(curSum) - 1);

        return res;
    }


}
